import entity.TreeNode;

import java.util.Collections;
import java.util.LinkedList;
import java.util.stream.Collectors;

public class PathSum {
    /*
    * 112. 路径总和
    * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。
    * 判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
    * 如果存在，返回 true ；否则，返回 false 。
    * 叶子节点 是指没有子节点的节点。
    *
    * 树中节点的数目在范围 [0, 5000] 内
    * -1000 <= Node.val <= 1000
    * -1000 <= targetSum <= 1000
    * */
    public static void main(String[] args){

    }

    // 我的想法：递归，深度优先，记录路径
    public boolean hasPathSum(TreeNode root, int targetSum){
        if(root == null)
            return false;
        // 判断是不是叶子节点
        if(root.left == null && root.right == null)
            return targetSum == root.val;

        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }

    // 迭代法 当然还是先序遍历
    public boolean mySolution2(TreeNode root, int targetSum){
        if(root == null)
            return false;
        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<Long> sums = new LinkedList<>();
        stack.add(root);
        sums.add(Long.valueOf(root.val));
        while (!stack.isEmpty()){
            root = stack.pollLast();
            Long sum = sums.pollLast();
            if(root.left == null && root.right == null){
                if(sum == targetSum)
                    return true;
            }
            if(root.right != null){
                stack.add(root.right);
                sums.add(sum + root.right.val);
            }
            if(root.left != null){
                stack.add(root.left);
                sums.add(sum + root.left.val);
            }
        }
        return false;
    }
}
